package leetcode.f101t200;

import leetcode.struct.TreeNode;

import java.util.Stack;

/**
 * 判断二叉树是否镜像
 * https://leetcode.com/problems/symmetric-tree/
 *
 * @author lichx
 * @createTime 2024/3/22 14:10
 */
public class Q101_SymmetricTree {

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        Stack<TreeNode> s = new Stack<>();
        Stack<TreeNode> z = new Stack<>();
        TreeNode l = root, r = root;
        while (l != null || !s.isEmpty()) {
            while (l != null) {
                if(r == null || l.val != r.val) {
                    return false;
                }
                s.push(l);
                z.push(r);
                l = l.left;
                r = r.right;

            }
            l = s.pop();
            r = z.pop();
            l = l.right;
            r = r.left;
        }
        return true;
    }

    public static void main(String[] args) {
        Q101_SymmetricTree bean = new Q101_SymmetricTree();
        System.out.println(bean.isSymmetric(new TreeNode(1, new TreeNode(2, new TreeNode(3), new TreeNode(4)), new TreeNode(2,
                new TreeNode(4), new TreeNode(3)))));
        System.out.println(bean.isSymmetric(new TreeNode(1, new TreeNode(2, new TreeNode(2), null),
                new TreeNode(2, new TreeNode(2), null))));
    }
}
